import javax.print.attribute.HashAttributeSet;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: mac
 * Date: 2022-10-30
 * Time: 9:40
 */
class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class Day12 {
    //897.递增顺序搜索树
    Stack<TreeNode> stack = new Stack<>();
    public void middleOrder(TreeNode root){
        if (root == null){
            return;
        }

        middleOrder(root.left);
        stack.push(root);
        middleOrder(root.right);
    }
    public TreeNode increasingBST(TreeNode root) {
        middleOrder(root);

        TreeNode node = stack.pop();
        TreeNode preNode = null;
        while (!stack.isEmpty()){
            preNode = stack.pop();
            preNode.right = node;
            node.left = null;
            node = preNode;
        }
        return node;
    }
    //1021.删除最外层的括号 - 标记

    //栈解法
    public String removeOuterParentheses(String s) {
        Stack<Character> stack = new Stack<>();
        char[] array = s.toCharArray();
        StringBuilder str = new StringBuilder();
        for (int i = 0; i < array.length; i++) {
            char c = array[i];
            if (c == ')'){
                stack.pop();
            }
            if (!stack.isEmpty()){
                str.append(c);
            }
            if (c == '('){
                stack.push(c);
            }
        }
        return str.toString();
    }

    //O(1)空间复杂度解法
    public String removeOuterParentheses1(String s) {
        StringBuilder str = new StringBuilder();
        int ret = 0;
        char[] array = s.toCharArray();
        for (int i = 0; i < array.length; i++) {
            char c = array[i];
            if (c == ')'){
                ret--;
            }
            if (ret > 0){
                str.append(c);
            }
            if (c == '('){
                ret++;
            }
        }
        return str.toString();
    }

    //1047.删除字符串中的所有相邻重复项 - 标记
    public String removeDuplicates1(String s) {
        char[] array = s.toCharArray();
        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            if (!stack.isEmpty()){
                if (stack.peek() == array[i]){
                    stack.pop();
                    continue;
                }
            }
            stack.push(array[i]);
        }
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()){
            sb.append(stack.pop());
        }
        sb.reverse();
        return sb.toString();
    }
    //更优解法
    public String removeDuplicates(String S) {
        char[] s = S.toCharArray();
        int top = -1;
        for (int i = 0; i < s.length; i++) {
            if (top == -1 || s[top] != s[i]){
                s[++top] = s[i];
            }else{
                top--;
            }
        }
        return String.valueOf(s, 0, top + 1);
    }

    //1475.商品折扣后的最终价格
    public int[] finalPrices(int[] prices) {
        for (int i = 0; i < prices.length; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                if (prices[i] >= prices[j]){
                    prices[i] -= prices[j];
                    break;
                }
            }
        }
        return prices;
    }

    //1544.整理字符串
    public String makeGood(String S) {
        char[] s = S.toCharArray();
        int top = -1;
        for (int i = 0; i < s.length; i++) {
            if (s[i] >= 'a' && s[i] <= 'z'){
                if (top == -1 || s[top] != s[i] - 32){
                    s[++top] = s[i];
                }else{
                    top--;
                }
            }else{
                if (top == -1 || s[top] != s[i] + 32){
                    s[++top] = s[i];
                }else{
                    top--;
                }
            }
        }
        return String.valueOf(s, 0, top + 1);
    }

    //1598.文件夹操作日志搜集器
    public int minOperations1(String[] logs) {
        Stack<String> stack = new Stack<>();
        for (String s : logs){
            if (s.compareTo("../") == 0){
                if (!stack.isEmpty()){
                    stack.pop();
                }
            }else if (s.compareTo("./") != 0){
                stack.push(s);
            }
        }
        return stack.size();
    }
    public int minOperations(String[] logs) {
        int top = 0;
        for (int i = 0; i < logs.length; i++) {
            if (logs[i].compareTo("../") == 0){
                if (top != 0){
                    top--;
                }
            } else if (logs[i].compareTo("./") != 0) {
                top++;
            }
        }
        return top;
    }
}





























